Zone of Algorithm

我觉得这个题甚至更难一点……
动态规划的思维还是得练……
为什么想不到呢……

心路历程

1. 毫无办法，不知道怎么做到“绝顶聪明”，不知道怎么枚举可能情况才叫聪明；
2. 猜测有蓝色就选择蓝色，然后模拟，发现有 hack；
   猜测最优策略之下两个人的选择轮数最多，发现不对，因为最优策略包括给别人出难题；
3. 知道是动态规划题，所以想怎么描述状态；
   想到当前剩余 的石头并且两个人各拿了 个红石头，是可以描述的；想到 ，就是选择 之后的情况；
4. 想着动态规划可以改装成搜索，然后就想怎么搜索，发现搜索的每一步完全不能保证选择的智商，所以放弃了这个想法；
5. 仍然不知道怎么说明最优情况，挂在这里了；

非常好奇那些第一次就看出来了的人是怎么想的，如果愿意分享请一定要在评论区说两句，我在这里 %%% Orz。

姜盼码出了他的猜想，然后 AC 了，然后我去问他怎么想的，就有了这份题解：

题目

• Alice 和 Bob 又在玩游戏。
• 在他们面前有 n 块石头排成一行，石头有红和蓝两种颜色。
• Alice 先手，每次每人从两端选择一端取出一块石头，谁先取出 k 块红色石头谁输掉。
• 假设 Alice 和 Bob 都是绝顶聪明的，求出最后谁获胜。
• ，红石头至少有 个。

题解

• 状态部分比较显然，因为肯定是一个子区间；
  而且情况只与“当前红石数量”“区间是截取的那一部分有关”；
  所以就有了 的状态设置；
  发现空间炸了，并且在 已知的情况下， 是可以算的；
  所以是不用保存的；
• 因为转移太复杂了，我没有办法找到一个确定的转移说明他就是好的；
  考虑记忆化搜索；
  我当时就判掉了搜索，因为没有办法保证每一步的智商；
• 但是没有关系；
  因为我可以枚举所有的状态，
  轮到 ，一旦发现存在无解方法，那么他能够操纵这个局面；
  轮到 ，一旦发现存在有解方法，那么她能够做出正确的选择；
  所以返回值就是有解无解的判断；
• 这就涉及“最优方案”的理解了，我们把一个具体的，困难的方法寻找，变成了一个可行性判断，因为只要可能做到，他们就一定可以做到。这是“绝顶聪明”的内涵。
• 然后记忆化比较板子，维护当前情况是否有解即可；

欸，那有的同学又要问了：

FSR，为什么有的时候我们就不考虑递推式的动态规划，而是用记忆化搜索？

一般而言，这种时候和路径相关：

• 每一次的选择，这个和选择路径相关；
• 数位 DP，这个也和每一步是有相关性的；
• 要求构造出可行解的；

这些可能可以改造成递推形式的，但是除非有特殊的优化需求，不建议改，因为容易错，复杂，而且和思路是倒着来的：

本题中，可能某一个人提前就结束了游戏，所以从 推过来的方法是很反逻辑的；

所以这个题还是非常好的（对我而言），虽然难度只有黄：

• 怎么判掉没有用的一维状态，练过了；
• 什么时候用记忆化搜索，复习了；
• 把最优策略转化为可行性，学到了；

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 355;

int n, k;
string s;
int f[MAXN][MAXN][MAXN];

inline bool dfs(int step, int l, int r, int cnt, int cur) {
    if (cnt == k)
        return false;
    if (cur - cnt == k)
        return true;
    if (f[l][r][cnt] != -1)
        return f[l][r][cnt];

    bool res1 = dfs(step + 1, l, r - 1, cnt + ((step & 1) && (s[r] == 'C')), cur + (s[r] == 'C'));
    bool res2 = dfs(step + 1, l + 1, r, cnt + ((step & 1) && (s[l] == 'C')), cur + (s[l] == 'C'));
    if (step & 1)
        return (f[l][r][cnt] = res1 || res2);
    return (f[l][r][cnt] = res1 && res2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k >> s;
    s = " " + s;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int x = 0; x <= n; ++x)
                f[i][j][x] = -1;
    cout << (dfs(1, 1, n, 0, 0) ? "DA" : "NE");
    return 0;
}

再次声明，请大佬不要吝惜自己的思路，分享一下自己是怎么从无到有想出来的，谢谢！（如果评论区装不下，其实写一篇题解更好！）